The present invention relates generally to the field of online transaction processing (OLTP), and more particularly to developing a highly concurrent, low-maintenance, in-memory data structure to support a wide spectrum of queries, including point and range queries.
OLTP is a class of information systems that facilitate and manage transaction-oriented applications, typically for data entry and retrieval transaction processing. The term OLTP is somewhat ambiguous; some understand a “transaction” in the context of computer or database transactions, while others define a “transaction” in terms of business or commercial transactions. OLTP has also been used to refer to processing in which the system responds immediately to user requests. An automated teller machine (ATM) for a bank is an example of a commercial transaction processing application. Online transaction processing applications are high throughput and insert or update-intensive in database management. OLTP applications can be used concurrently by a plurality of users. The key goals of OLTP applications are availability, speed, concurrency, and recoverability. Like many modern online information technology solutions, some systems require offline maintenance, which affects the cost-benefit analysis of online transaction processing systems.
A range query is a common database operation that retrieves records where some value is between an upper and lower boundary. For example, a range query may request a list of employees with three to five years of experience. Range queries are unusual because it is not generally known in advance how many entries a range query will return, or if it will return any entries at all. Many other queries, such as the top ten most senior employees, or the newest employee, can be done more efficiently, because there is an upper bound to the number of results returned. A query that returns exactly one result is sometimes called a singleton.
In data structures, a range query requires preprocessing of some input data into a data structure to efficiently answer any number of queries on any subset of the input. Particularly, there is a group of problems that have been extensively studied where the input is an array of unsorted numbers and a query includes computing some function on a specific range of the array.
In computer science, a data structure is a particular way of organizing data in a computer so the data can be used efficiently. Different kinds of data structures are suited to different kinds of applications, and some are highly specialized to specific tasks. For example, some databases use B-tree indexes for small percentages of data retrieval and compilers and other databases use dynamic hash tables for data retrieval. Data structures provide a means to manage large amounts of data efficiently for uses such as large databases and internet indexing services. Usually efficient data structures are key to designing efficient algorithms. Some formal design methods and programming languages emphasize data structures, rather than algorithms, as the key organizing factor in software design. Storing and retrieving can be carried out on data stored in both main memory and in secondary memory.